House Robber III

LeetCode 337 | Difficulty: Medium

Medium

Problem Description

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return *the maximum amount of money the thief can rob without alerting the police*.

Example 1:

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

Constraints:

- The number of nodes in the tree is in the range `[1, 10^4]`.

- `0 <= Node.val <= 10^4`

Topics: Dynamic Programming, Tree, Depth-First Search, Binary Tree

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

---

Solutions

Solution 1: C# (Best: 100 ms)

Metric	Value
Runtime	100 ms
Memory	25 MB
Date	2019-03-21

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int Rob(TreeNode root) {
       return RobSub(root, new Dictionary<TreeNode, int> ());
    
}

public int RobSub (TreeNode root, Dictionary<TreeNode, int> map)
{
    if(root == null) return 0;
    if(map.ContainsKey(root)) return map[root];
    
    int val = 0;
    if(root.left != null) 
    {
        val += RobSub(root.left.left, map) + RobSub(root.left.right, map);
    }
    if(root.right != null)
    {
        val += RobSub(root.right.left, map) + RobSub(root.right.right, map);
    }
    
    val =  Math.Max(val + root.val, RobSub(root.left, map) + RobSub(root.right, map));      
    map.Add(root, val);
    return val; 
    }
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$
Tree Traversal	$O(n)$	$O(h)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.